package org.ww.algorithm.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class HuffumanTree {
    public static void main(String[] args) {
        int arr[]=new int[]{3,1,5,9,1,0,22};
        List<Node> huffuman = createHuffuman(arr);
        preOrder(huffuman.get(0));
    }

    public static void preOrder(Node node){
        if(node!=null){
            node.preOrder();
        }else{
            System.out.println("");
        }
    }

    public static List<Node>  createHuffuman(int arr[]){
        List<Node> nodeList=new ArrayList<>();


        for(int value:arr){
            nodeList.add(new Node(value));
        }
        while(nodeList.size()>1){
            Collections.sort(nodeList);
            Node leftNode = nodeList.get(0);
            Node rightNode = nodeList.get(1);
            Node newNode = new Node(leftNode.value + rightNode.value);
            newNode.left=leftNode;
            newNode.right=rightNode;
            nodeList.add(newNode);

            nodeList.remove(leftNode);
            nodeList.remove(rightNode);
        }

        return nodeList;



    }

}

class Node implements Comparable<Node>{
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    public void preOrder(){
        System.out.println(this);
        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    @Override
    public String toString() {
        return "Node[" +
                "value=" + value +
                ']';
    }

    @Override
    public int compareTo(Node o) {
        //从小到大
        return this.value-o.value;
    }
}
